Variable Subsequences

Memory limit: 32 MB

We are looking for variable subsequences of a given sequence . A subsequence is obtained from a sequence by removing any number of its terms (possibly 0). More formally, a subsequence of the sequence is any sequence A variable subsequence is a subsequence such that every two its consecutive terms are different. For example, the sequence is a variable subsequence of the sequence .

We would like to know how many distinct and nonempty variable subsequences of a given sequence are there. Two subsequences are considered distinct if the sets of positions in corresponding to them are different. For instance, the sequence contains two distinct variable subsequences of the form .

Input

The first line of the standard input contains one integer (), denoting the length of the sequence . The second line contains integers ().

Output

Your program should write to the first and only line of the standard output a single integer: the number of nonempty variable subsequences of the input sequence modulo .

Example

For the input data:

4
1 2 1 1

the correct result is:

9

Explanation of the example: The considered subsequences of the sequence are:

• - counted three times,
• - counted once,
• - counted once,
• - counted twice and
• - counted twice.

Task author: Jakub Radoszewski.